#include <iostream>
#include <string>
using namespace std;

void getNext(string patt, int* next)
{
    int pre_fix = 1, i = 3;
    next[1] = 0;
    next[2] = 1;
    while (patt[i-1])
    {
        if (patt[pre_fix] == patt[i])
            next[i++] = ++pre_fix;
        else
        {
            if (next[pre_fix] == 1)
            {
                next[i++] = 1;
            }
            else
                pre_fix = next[pre_fix];
        }
    }
}
void getNextVal(string patt, int* nextval)
{
    int i=1,j=0;
    nextval[1] = 0 ;
    while (i<patt.length())
    {
        if(j==0||patt[i]==patt[j]){
            i++;j++;
            if (patt[i]!=patt[j])
            {
                nextval[i] = j;
            }
            else nextval[i]=nextval[j];
        }
        else j = nextval[j];
    }
}

int KMP_search(string des, string patt)
{
    int i=0, j=0, next[patt.length()+1];
    getNext(patt, next);
    while (i<des.size())
    {
        if (des[i]==patt[j])
        {
            i++;j++;
        }else if(j>1){
            j= next[j+1]-1;
        }else i++;
        
        if (j==patt.size()){
            return i-j+1;
        }
    }
    return -1;
}

void init(){
printf("%d",KMP_search("11sws1ssws1s", "1sws1s"));
}

int main(int argc, char const *argv[])
{
    init();
    return 0;
}
